package Greedy;

import java.util.HashSet;
import java.util.Set;

public class _392_IsSubsequence {
    //solution 1:using longest common subsequence method
    //fail:runtime error,over stack flow
    public boolean isSubsequence0(String s, String t) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < t.length(); i++) {
            set.add(t.charAt(i));
        }
        for (int i = 0; i < s.length(); i++) {
            if (!set.contains(s.charAt(i))) {
                return false;
            }
        }
        return s.length() == lcsM(s, t, s.length() - 1, t.length() - 1);
    }

    public int lcsM(String word1, String word2, int pos1, int pos2) {
        if (pos1 < 0 || pos2 < 0) {
            return 0;
        }
        if (word1.charAt(pos1) == word2.charAt(pos2)) {
            return  1 + lcsM(word1, word2, pos1 - 1, pos2 - 1);
        } else {
            return  Math.max(lcsM(word1, word2, pos1-1, pos2), lcsM(word1, word2, pos1, pos2 - 1));
        }
    }

    //hint:find every letter in s and record the letter's position,then start the next find with the position+1
    public boolean isSubsequence(String s, String t) {
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            int tempPos = t.indexOf(s.charAt(i), pos);
            if (tempPos == -1) {
                return false;
            } else {
                pos = tempPos+1;
            }
        }
        return true;
    }
}
